package org.example.leetcode.addon.lc112;

import org.example.util.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;

        Deque<TreeNode> nodes = new LinkedList<>();
        Deque<Integer> vals = new LinkedList<>();
        nodes.push(root);
        vals.push(root.val);

        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int sum = vals.pop();

            if (node.left == null && node.right == null && sum == targetSum) {
                return true;
            }

            if (node.left != null) {
                nodes.push(node.left);
                vals.push(sum + node.left.val);
            }

            if (node.right != null) {
                nodes.push(node.right);
                vals.push(sum + node.right.val);
            }

        }

        return false;
    }
}
